import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution1().solveNQueens(1));
        System.out.println(new Solution1().solveNQueens(4));
    }
}

//基本回溯
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        backtracking(n, new ArrayList<>(n), ans);
        return ans;
    }

    void backtracking(int n, List<StringBuilder> cur, List<List<String>> ans) {
        if (cur.size() == n) {
            List<String> s = new ArrayList<>(n);
            cur.forEach((row) -> s.add(row.toString()));
            ans.add(s);
            return;
        }

        //init row
        StringBuilder rowStr = new StringBuilder();
        for (int i = 0; i < n; i++) {
            rowStr.append('.');
        }

        cur.add(rowStr);
        //recursion
        for (int col = 0; col < n; col++) {
            if (isPosValid(n, cur, col)) {
                rowStr.setCharAt(col, 'Q');
                backtracking(n, cur, ans);
                rowStr.setCharAt(col, '.');
            }
            ;
        }
        cur.remove(cur.size() - 1);
    }

    private boolean isPosValid(int n, List<StringBuilder> cur, int col) {
        int curRow = cur.size() - 1;
        for (int row = 0; row < curRow; row++) {
            if (cur.get(row).charAt(col) == 'Q') {
                return false;
            }
            int upperLeftCol = col - curRow + row;
            if (upperLeftCol >= 0 && cur.get(row).charAt(upperLeftCol) == 'Q') {
                return false;
            }
            int upperRightCol = col + curRow - row;
            if (upperRightCol < n && cur.get(row).charAt(upperRightCol) == 'Q') {
                return false;
            }
        }
        return true;
    }
}

//基于位运算的回溯
class Solution1 {
    public List<List<String>> solveNQueens(int n) {
        int[] queens = new int[n];
        List<List<String>> ansList = new ArrayList<>();
        backtracking(n, queens, 0, 0, 0, 0, ansList);
        return ansList;
    }

    void backtracking(int n, int[] queens, int row, int colInvalid, int diag1Invalid, int diag2Invalid,
                      List<List<String>> ansList) {
        if (row == n) {
            List<String> ans = makeAns(n, queens);
            ansList.add(ans);
            return;
        }

        int allPossiblePos = (1 << n) - 1;
        int validPos = allPossiblePos & ~(colInvalid | diag1Invalid | diag2Invalid);
        while (validPos != 0) {
            int queenPos = validPos & (-validPos);
            int queenCol = Integer.bitCount(queenPos - 1);
            queens[row] = queenCol;
            backtracking(n, queens, row + 1, colInvalid | queenPos,
                    (diag1Invalid | queenPos) << 1, (diag2Invalid | queenPos) >> 1, ansList);
            validPos = validPos & (validPos - 1);
        }
    }

    private List<String> makeAns(int n, int[] queens) {
        List<String> ans = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            StringBuilder rowSb = new StringBuilder(n);
            for (int j = 0; j < n; j++) {
                rowSb.append('.');
            }
            rowSb.setCharAt(queens[i], 'Q');
            ans.add(rowSb.toString());
        }
        return ans;
    }
}

